package com.springchang.algorithm.floyd;

import java.util.Arrays;

/**
 * 弗洛伊德算法
 * @author 张翠山
 * @date 2021/10/06
 */
public class FloydWarshall {

    public static final int N = 65535;

    public static void main(String[] args) {
        //先构造图的顶点,存储在一维数组里面
        char[] vertex = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};

        //构造图的边，存储在邻接矩阵里面
        int[][] matrix = new int[][] {
                {0, 5, 7, N, N, N, 2},
                {5, 0, N, 9, N,N, 3},
                {7, N, 0,N, 8, N, N},
                {N, 9, N, 0, N, 4, N},
                {N, N, 8, N, 0, 5, 4},
                {N, N, N, 4, 5, 0, 6},
                {2, 3, N, N, 4, 6, 0}
        };

        //存放各顶点距离的二维数组
        int[][] dist = new int[vertex.length][vertex.length];
        //初始化状态和matrix一致
        copy(matrix, dist);

        //创建一个二维数组存储前驱数据
        int[][] pre = new int[vertex.length][vertex.length];
        for (int i = 0; i < pre.length; i++) {
            Arrays.fill(pre[i], i);
        }

        //弗洛伊德算法开始,开始遍历中间点
        for (int k = 0; k < vertex.length; k++) {
            //开始遍历起始点
            for (int i = 0; i < vertex.length; i++) {
                //开始遍历结束点
                for (int j = 0; j < vertex.length; j++) {
                    //比较顶点下标i->j的直达路劲和以k作为中间点路劲，谁短
                    if(dist[i][k]+dist[k][j] < dist[i][j]) {
                        //如果以k作为中间点的距离小于直连的距离，则更新距离表和前驱表
                        dist[i][j] = dist[i][k]+dist[k][j];
                        //更新前驱表
                        pre[i][j] = pre[k][j];
                    }
                }
            }
        }

        //打印距离表
        System.out.println("--------------顶点距离--------------");
        print(dist);

        //打印顶点前驱表
        System.out.println("--------------顶点前驱--------------");
        print(pre);

        //优化输出
        for (int k = 0; k < dist.length; k++) {
            for (int i = 0; i < dist.length; i++) {
                System.out.print(vertex[pre[k][i]] + " ");
            }
            System.out.println();

            //输出dis数组一行的数据
            for (int i = 0; i < dist.length; i++) {
                System.out.print("("+vertex[k]+"->"+vertex[i]+":"+dist[k][i]+")");
            }
            System.out.println();
            System.out.println();
        }

        System.out.println();

        int start = 4;
        int end = 1;
        System.out.println(vertex[start]+"->"+vertex[end]+"最短路劲长度："+dist[start][end]);
        System.out.print(vertex[start]+"->"+vertex[end]+"最短路劲："+vertex[end]);
        //当前驱节点不等于起始点，继续遍历
        while (end != start) {
            System.out.print("->" + vertex[pre[start][end]]);
            end = pre[start][end];
        }
        System.out.println();
    }

    public static void print(int[][] matrix) {

        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                System.out.printf("%5d", matrix[i][j]);
            }
            System.out.println();
        }
    }

    /**
     * 使用 System.arraycopy 方法
     *
     * @param sourceArr 源数组
     * @param destArr   目标数组
     */
    public static void copy(int[][] sourceArr, int[][] destArr) {
        for (int i = 0; i < sourceArr.length; i++) {
            if (sourceArr[i].length >= 0) {
                System.arraycopy(sourceArr[i], 0, destArr[i], 0, sourceArr[i].length);
            }
        }
    }

}
